#pragma once

#include "TableColumn.h"
#include "SortFunction.h"

namespace qb{
	namespace ht{
		struct SORTPOS{
			int left;
			int right;
			SORTPOS() :left(0), right(0){}
		};
		class TaskCache;
		class ThreadPool;
		class ThreadSorter{							// 单例模式
		protected:
			class SortRangeStack{
                std::vector<SORTPOS> m_ranges;		// 只是作为一个可扩展的整块内存使用
				int					m_count;		// 指示当前stack中有多少个是有效的
			public:
				void Clear(){ m_count = 0; }
				bool Pop(SORTPOS& q);
				void Add(int begin, int end);
			};
			unsigned char*			sort_;			// 数据
			int						m_temp_size;	// m_comp_temp的实际内存大小
			int						m_record_size;	// m_sort_buffer->GetRecordSize()
			char*					m_comp_temp;	// 至少m_sort_buffer->GetRecordSize()大小，用于比较
			int						granularity_;	// 多线程快排的时候，约定每多少个
			int						first_granul_;	// 主线程负责排序的开始个数
			int						range_;			// 当前排序的记录个数	
			int						comp_count_;	// 比较的次数
			int						swap_count_;	// 交换的次数
			TaskCache*				m_task_cache;	// 当前多线程分配的任务缓存
			SortRangeStack			m_stack;		// 将递归改造为使用栈
			ThreadPool*				m_thread_pool;	// 专门用来多线程排序的线程池
		public:
			ThreadSorter();
			~ThreadSorter();

			// 对外提供两种接口,ThreadSort是多线程快排，是普通的快排
			void ThreadSort(void* base, unsigned num, unsigned width, FuncCompColumn comp);
			void QuickSort(void* base, unsigned num, unsigned width, FuncCompColumn comp);

			// CheckSortResult是在数据还存在的情况下对排序结果进行检查
			void CheckSortResult();
		protected:
			ThreadPool* GetThreadPool();
			/*
			LoadSortColumns：将当前user的多重排序列和rid的数据读取出来作为一张表放在内存中
			rid放在开头，内存为 rid,排序列0，排序列1，排序列2，...
			PrepareTempBuffer：准备排序过程中用到的数据
			UpdateIndex：将排序好的row-->rid更新到user中
			*/
			bool PrepareTempBuffer(int nsize);
			/*
			主线程和子线程都使用ThreadSortFunc来对指定段排序，通过调用SortImpl来实现
			QuickSort排序的时候使用StaticCompareColumns来对两个记录进行比较
			StaticCompareColumns又调用实例函数CompareColumns对两个记录进行比较
			*/
			static void ThreadSortFunc(void* p);
			static int StaticCompareColumns(ThreadSorter* sd, const void* pSortData1, const void* pSortData2);
			static int StaticCompareColumns2(void* context, const void* pSortData1, const void* pSortData2);
			virtual int CompareColumns(const void* pSortData1, const void* pSortData2) = 0;

			/*
			SplitTask用于使用栈而不是递归来将整个序列分段并提交给线程池来排序
			Partition用于将给定序列划分为三段，段内不排序，段与段之间排好序
			AddTask用于将前后两段序列提交给线程池来排序
			*/
			void SplitTask(char* a, int w, unsigned int p, unsigned int r, FuncCompColumn comp_func_);
			SORTPOS Partition(char* arr, int width, int left, int right, FuncCompColumn comp_func_);
			void AddTask(char* a, int w, unsigned int p, unsigned int r, FuncCompColumn comp);

			// 排序用到的交换两个记录内存的交换函数，使用m_swap_temp内存
			inline void SwapMemory(char *a, char *b, unsigned width);

			// 当快排QuickSort到最后阶段剩下少量数据的时候，使用此算法，速度更快
			void ShortSort(char *lo, char *hi, unsigned width, FuncCompColumn comp);


		};
	}
}

